Graphes probabilistes

Les graphes sont un moyen efficace de représenter des problèmes probabilistes que l'on avait l’habitude de représenter avec des arbres (qui sont un autre type de graphes).

On considère un système qui évolue et ne peut occuper qu’un nombre fini d’états, l’état à une étape  \(n\) ne dépendant que de l’état à l’étape précédente \(n-1\) .

Définition

Un graphe probabiliste est un graphe orienté pondéré par des réels compris entre  \(0\) et \(1\) , et dans lequel la somme des poids des arêtes issues de chaque sommet est égale à \(1\) .

Exemple

Voici un graphe à deux états  \(\text A\) et  \(\text B\) :

La somme des poids des arêtes issues de  \(\text A\) est \(0,22 + 0,78 =1\) .
La somme des poids des arêtes issues de  \(\text B\) est \(0,53+0,47=1\) .
Donc il s’agit bien d’un graphe probabiliste, où à chaque étape le système est soit à l’état  \(\text A\) , soit à l’état \(\text B\) .

À chaque étape  \(n\) , la probabilité que le système soit à l’état  \(\text A\) est  \(P(\text A_n)=p_n\) et la probabilité qu’il soit à l’état  \(\text B\) est \(P(\text B_n)=1-P(\text A_n)=1-p_n\) .

Et on a aussi, pour tout entier \(n\) , 
\(\begin{align}P_{\text A_n}(\text A_{n+1})=0,22\\P_{\text A_n}(\text B_{n+1})=0,78\\P_{\text B_n}(\text A_{n+1})=0,53\\P_{\text B_n}(\text B_{n+1})=0,47\\\end{align}\)

Une autre représentation pour cet exemple est donnée par l'arbre :